home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 08 - 1992 / 08.06 Oct 92 / Programmers' Challenge / Zick, Aaron (Winner) / pegs.c
Encoding:
C/C++ Source or Header  |  1994-11-06  |  7.6 KB  |  237 lines  |  [TEXT/KAHL]
  1.  
  2. /* Max holes per side of the peg board. */
  3. #define HOLES 13
  4.  
  5. void GetPerimeter( Point thePegs[], short numPegs,
  6.     Point outerPegs[], short sideLast[] );
  7. void GetEdgePegs( Point outerPegs[], short test, short last,
  8.     Point edgePegs[], short *numEdgePegs );
  9. void CheckEdgePegs( Point edgePegs[], short *numEdgePegs,
  10.     Point newPeg, short first );
  11. void IntegrateArea( Point edgePegs[], short numEdgePegs,
  12.     Fixed *area ); 
  13.  
  14. /*******************************************************/
  15.  
  16. /* BandedPegs takes an array of points representing
  17.  * pegs on a pegboard and returns an array of points
  18.  * representing the pegs that would be touched by a
  19.  * rubber band surrounding as many pegs as possible.
  20.  * It also returns the area thus surrounded. */
  21.  
  22. void BandedPegs( short numPegs, Point thePegs[],
  23.     short *numEdgePegs, Point edgePegs[], Fixed *area )
  24. {
  25.     Point   outerPegs[4*(HOLES-1)+1];
  26.     short   sideLast[4], first, last, i;
  27.  
  28.     if( numPegs > 3 ) {
  29.     
  30.         GetPerimeter( thePegs, numPegs, outerPegs, sideLast );
  31.         
  32.         /* Initialize some variables and march around
  33.          * the sides of the board. */
  34.         *numEdgePegs = first = i = 0;
  35.         do {
  36.             /* If there's at least one new peg along the
  37.              * column tops (bottoms), see which ones contact
  38.              * the rubber band. */
  39.             last = sideLast[i++];
  40.             if( first < last ) {
  41.                 GetEdgePegs( outerPegs, first, last, edgePegs,
  42.                     numEdgePegs );
  43.                 first = last;
  44.             }
  45.             /* Count all pegs from the last (first) column
  46.              * as edge pegs. */
  47.             last = sideLast[i++];
  48.             while( first < last )
  49.                 edgePegs[(*numEdgePegs)++] = outerPegs[first++];
  50.         } while( i < 4 ); /* Repeat for four sides. */
  51.     }
  52.     else { 
  53.         /* With 3 or fewer pegs, all will touch the rubber band. */
  54.         *numEdgePegs = numPegs;
  55.         for( i = 0; i < numPegs; i++ ) edgePegs[i] = thePegs[i];
  56.         if( numPegs < 3 ) {
  57.             /* With less than 3 pegs, area must be 0. */
  58.             *area = 0;
  59.             return;
  60.         }
  61.     }
  62.     
  63.     IntegrateArea( edgePegs, *numEdgePegs, area );
  64.     
  65.     /* If there are more than 3 pegs, and they are all
  66.      * in a straight line (indicated by a zero area),
  67.      * the above algorithm will have counted the interior
  68.      * points twice.  The following will remove the
  69.      * redundant set of interior points.  Note that
  70.      * it's also okay for 3 pegs, but no fewer. */
  71.     if( *area == 0 )
  72.         *numEdgePegs = (*numEdgePegs + 3)/2;
  73. }
  74.  
  75. /*******************************************************/
  76.  
  77. /* This function finds the pegs which roughly
  78.  * define the four sides of the rubber band. */
  79.  
  80. void GetPerimeter( Point thePegs[], short numPegs,
  81.     Point outerPegs[], short sideLast[] )
  82. {
  83.     short   colmin[HOLES], colmax[HOLES],
  84.             rowmin[HOLES], rowmax[HOLES],
  85.             col, row, col1, col2, n;
  86.  
  87.     for( n = 0; n < HOLES; n++  ) {
  88.         colmin[n] = rowmin[n] = HOLES;
  89.         colmax[n] = rowmax[n] = -1;
  90.     }
  91.     /* Check each peg to see if it sets a new extreme
  92.     * in any row or column. */
  93.     for( n = 0; n < numPegs; n++ ) {
  94.         row = thePegs[n].v;
  95.         col = thePegs[n].h;
  96.         if( col < colmin[row] ) colmin[row] = col;
  97.         if( col > colmax[row] ) colmax[row] = col;
  98.         if( row < rowmin[col] ) rowmin[col] = row;
  99.         if( row > rowmax[col] ) rowmax[col] = row;
  100.     }
  101.     /* Collect the pegs at the tops of each column. */
  102.     n = -1;
  103.     for( col = 0; col < HOLES; col++ ) {
  104.         if( (row = rowmin[col]) < HOLES ) {
  105.             outerPegs[++n].v = row;
  106.             outerPegs[n].h = col;
  107.         }
  108.     }
  109.     sideLast[0] = n;
  110.     col1 = outerPegs[0].h;
  111.     col2 = outerPegs[n].h;
  112.     /* Collect all but the top peg of the last column,
  113.      * from top to bottom. */
  114.     for( row = rowmin[col2] + 1; row <= rowmax[col2]; row++ ) {
  115.         if( colmax[row] == col2 ) {
  116.             outerPegs[++n].v = row;
  117.             outerPegs[n].h = col2;
  118.         }
  119.     }
  120.     sideLast[1] = n;
  121.     /* From last to first, collect the pegs at the
  122.      * bottoms of all but the last column. */
  123.     for( col = col2 - 1; col >= col1; col-- ) {
  124.         if( (row = rowmax[col]) >= 0 ) {
  125.             outerPegs[++n].v = row;
  126.             outerPegs[n].h = col;
  127.         }
  128.     }
  129.     sideLast[2] = n;
  130.     /* Collect all but the bottom peg of the first column,
  131.      * from bottom to top. */
  132.     for( row = rowmax[col1] - 1; row >= rowmin[col1]; row-- ) {
  133.         if( colmin[row] == col1 ) {
  134.             outerPegs[++n].v = row;
  135.             outerPegs[n].h = col1;
  136.         }
  137.     }
  138.     sideLast[3] = n;
  139. }
  140.  
  141. /*******************************************************/
  142.  
  143. /* This function finds the pegs which would push
  144.  * a rubber band to the left of a line between a
  145.  * given starting point and a given ending point.
  146.  * It counts the starting point (but not the
  147.  * ending point) as such a peg. */
  148.  
  149. void GetEdgePegs( Point outerPegs[], short test, short last,
  150.                   Point edgePegs[], short *numEdgePegs )
  151. {
  152.     Point   testPeg, backPeg, nextPeg;
  153.     short   convex, first;
  154.  
  155.     first = *numEdgePegs;
  156.  
  157.     backPeg = edgePegs[(*numEdgePegs)++] = outerPegs[test];
  158.     nextPeg = outerPegs[last];
  159.     /* Loop through the array of outerPegs from the
  160.      * one after the starting point to the one just
  161.      * before the ending point. */
  162.     while( ++test < last ) {
  163.         testPeg = outerPegs[test];
  164.         /* See if the path connecting backPeg, testPeg,
  165.          * and nextPeg is convex, straight, or concave. */
  166.         if( (convex = (nextPeg.v-backPeg.v)*(testPeg.h-backPeg.h)
  167.             -(testPeg.v-backPeg.v)*(nextPeg.h-backPeg.h)) >= 0 ) {
  168.             /* If convex or straight, count the test
  169.              * peg as an edge peg. */
  170.             edgePegs[(*numEdgePegs)++] = backPeg = testPeg;
  171.             /* If convex, the rubber band's path will change,
  172.              * so we need to check previous edge pegs to see
  173.              * if they are still edge pegs. */
  174.             if( convex > 0 )
  175.                 CheckEdgePegs( edgePegs, numEdgePegs, testPeg, first );
  176.         }
  177.     }
  178. }
  179.  
  180. /*******************************************************/
  181.  
  182. /* If a peg just added to the list of edge pegs
  183.  * has extended the rubber band, this routine will
  184.  * search backward through the list, throwing out pegs
  185.  * that are no longer contacted, until it finds one
  186.  * that still is. */
  187.  
  188. void CheckEdgePegs( Point edgePegs[], short *numEdgePegs,
  189.                     Point newPeg, short first )
  190. {
  191.     Point   testPeg, backPeg;
  192.     short   test;
  193.  
  194.     test = *numEdgePegs - 1;
  195.     /* Loop backward through the list of edge pegs,
  196.      * starting with the one before that just added,
  197.      * stopping before the first that can't be removed. */
  198.     while( --test > first ) {
  199.         testPeg = edgePegs[test];
  200.         backPeg = edgePegs[test-1];
  201.         /* If the path between newPeg, testPeg,
  202.          * and backPeg is concave, remove the peg. */
  203.         if( (newPeg.v-backPeg.v)*(testPeg.h-backPeg.h)
  204.             -(testPeg.v-backPeg.v)*(newPeg.h-backPeg.h) < 0 )
  205.             edgePegs[test] = edgePegs[--(*numEdgePegs)];
  206.         else
  207.             return;
  208.     }
  209. }
  210.  
  211. /*******************************************************/
  212.  
  213. /* This function integrates the area enclosed
  214.  * by a rubber band. */
  215.  
  216. void IntegrateArea( Point edgePegs[],
  217.     short numEdgePegs, Fixed *area ) 
  218. {
  219.     Point   thePeg, lastPeg;
  220.     long    integral = 0;
  221.     short   i;
  222.     /* Starting and ending with the last peg,
  223.      * integrate double the area under the closed path. */
  224.     lastPeg = edgePegs[numEdgePegs-1];
  225.     for( i = 0; i < numEdgePegs; i++ ) {
  226.         thePeg = edgePegs[i];
  227.         integral += (thePeg.h + lastPeg.h)*(thePeg.v - lastPeg.v);
  228.         lastPeg = thePeg;
  229.     }
  230.     /* Correct a negative integral if the path was
  231.      * counterclockwise. */
  232.     if( integral < 0 ) integral = -integral;
  233.     /* By shifting, simultaneously halve the integral
  234.      * and convert it to a fixed. */
  235.     *area = (Fixed)( integral << 15 );
  236. }
  237.